package 动态规划;
//https://www.nowcoder.com/practice/23462ed010024fcabb7dbd3df57c715e?tpId=46&tqId=29115&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
public class 带权值的最小路径和 {
    public int minPathSum (int[][] grid) {
        // write code here
        for (int i = 1 ; i < grid.length ; i ++){
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        for (int i = 1 ; i < grid[0].length ; i ++){
            grid[0][i] = grid[0][i - 1] + grid[0][i];
        }
        for (int i = 1 ; i < grid.length ; i ++){
            for (int j = 1 ; j < grid[0].length ; j ++){
                grid[i][j] = Math.min(grid[i - 1][j] , grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }

}
